# JZ15 反转链表
#
# 描述
# 输入一个链表，反转链表后，输出新链表的表头。
# 示例1
# 输入：
# {1,2,3}
# 返回值：
# {3,2,1}

# 核心代码
# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    # 返回ListNode
    def ReverseList(self, pHead):
        # 辅助栈
        if not pHead: return None
        stack = []
        # 进栈
        while pHead:
            stack.append(pHead)
            pHead = pHead.next
        # 出栈 先出来头节点
        pHead = stack.pop()
        root = pHead
        while stack:
            tempNode = stack.pop()
            pHead.next = tempNode
            pHead = pHead.next
        # 最后一个元素next为空
        pHead.next = None
        return root

        # 函数 数组形式输出
#         res=[]
#         res = list(reversed(res))
#         for i in range(len(res) - 1):
#              res[i].next = res[i + 1] # 根据取反后的数组顺序重新构建链表
#         res[-1].next = None # 注意将最后一个元素的后继节点置为空，否则会出现环
#         return res[0]